nLab total preorder

Redirected from "total preorders".

Contents

 Definition

Total preorders

A total preorder or linear preorder or preference relation or (non-strict) weak order is a preorder whose posetal reflection is a total order, or equivalently it is a preorder which is also a total relation:

  • for all elements xx and yy, xyx \leq y or yxy \leq x

In category theory, a total preorder is a thin category CC for which given two objects xCx \in C and yCy \in C, there exists a morphism in either hom(x,y)\mathrm{hom}(x, y) or hom(y,x)\mathrm{hom}(y, x). In fact, every total preorder is an unbounded prelattice, a thin locally cartesian category whose opposite category is also locally cartesian.

Cotransitive preorders

A cotransitive preorder on a set SS is a preorder \leq which satisfies cotransitivity/weak linearity:

  • for all xSx \in S, ySy \in S, and zSz \in S, xzx \leq z implies that xyx \leq y or yzy \leq z.

 Relation between the two definitions

Theorem

Cotransitive preorders are total preorders.

Proof

Cotransitivity of \leq says that for all xSx \in S and ySy \in S, xxx \leq x implies that xyx \leq y or yxy \leq x, and reflexivity says that for all xx, xxx \leq x is always true. This implies that for all xx and yy, xyx \leq y or yxy \leq x is always true, which is precisely the condition of totality. Since cotransitive preorders are preorders, this implies that cotransitive preorders are total preorders.

Lemma

Cotransitive partial orders are total orders.

[TBD: figure out if total preorders are cotransitive preorders.]

Theorem

Total orders are cotransitive partial orders.

Strict total preorders

Similar to total orders, one could make a distinction between the usual notion of total preorder, and strict total preorders?, which are the irreflexive version of total preorders, and are defined as a strict preorder which is weakly linear and asymmetric.

Using excluded middle, one can move between total preorders and strict total preorders using negation; that is, the negation of a total preorder is a strict total preorder and vice versa. Actually one usually swaps the order too, as follows:

  • xyx \leq y iff yxy \nless x;
  • x<yx \lt y iff yxy \nleq x.

To prove this, it's enough to see that the properties of a strict total preorder are dual to the properties of a total preorder, as follows:

strict total preordertotal preorder
irreflexivityreflexivity
asymmetrytotality
transitivityweak linearity
weak linearitytransitivity

In classical mathematics, the distinction between total preorders and strict total preorders is merely a terminological technicality, which is not always observed; more precisely, there is a natural bijection between the set of total preorders on a given set SS and the set of strict total preorders on SS, and one distinguishes them by their notation.

In constructive mathematics, however, they are irreducibly different. To be specific, if one starts with a total preorder \leq and defines <\lt as above, then weak linearity does not follow; and if one starts with a strict total preorder <\lt and defines \leq as above, then totality does not follow. Nevertheless, at least \leq will be a preorder, and least <\lt will be a strict preorder.

 Examples

An example of a set with a total preorder are the dual rational numbers [ϵ]/ϵ 2\mathbb{Q}[\epsilon]/\epsilon^2. The dual rational numbers have a strict weak order <\lt given by

(a+bϵ<c+dϵ)(a<c)(a + b \epsilon \lt c + d \epsilon) \iff (a \lt c)

for rational numbers aa, bb, cc, and dd. This strict weak order is not connected because 0ϵ0 \neq \epsilon, and thus the negation of the strict weak order, ab¬(b<a)a \leq b \coloneqq \neg(b \lt a), is not antisymmetric. However, \leq is a total preorder, because the strict weak order <\lt is irreflexive, weakly linear, transitive, and asymmetric, which implies that \leq is reflexive, transitive, and total.

More generally, any ordered local ring with strict weak order <\lt has a total preorder \leq defined by negation of <\lt. The quotient ordered field by the ideal of non-invertible elements results in a total preorder \leq which is also a total order. In constructive mathematics one has to make sure that <\lt is also decidable.

References

Last revised on December 26, 2023 at 04:33:22. See the history of this page for a list of all contributions to it.